//
//  ProblemMS0107.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/17.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 面试题 01.07. 旋转矩阵
 给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
 不占用额外内存空间能否做到？
 
 示例 1:
  给定 matrix =
     [
       [1,2,3],
       [4,5,6],
       [7,8,9]
     ],
  原地旋转输入矩阵，使其变为:
     [
       [7,4,1],
       [8,5,2],
       [9,6,3]
     ]
 示例 2:
  给定 matrix =
     [
       [ 5, 1, 9,11],
       [ 2, 4, 8,10],
       [13, 3, 6, 7],
       [15,14,12,16]
     ],
  原地旋转输入矩阵，使其变为:
     [
       [15,13, 2, 5],
       [14, 3, 4, 1],
       [12, 6, 8, 9],
       [16, 7,10,11]
     ]
 */
@objcMembers class ProblemMS0107: NSObject {
    func solution() {
        var list = [
            [1,2,3],
            [4,5,6],
            [7,8,9]
          ]
        rotate(&list)
        print(list)
    }
    
    /*
     方法一：辅助数组
     原理：
     [[1, 2, 3, 4]
      [*, *, *, *]
      [*, *, *, *]
      [*, *, *, *]]
     --->
     [[*, *, *, 1]
      [*, *, *, 2]
      [*, *, *, 3]
      [*, *, *, 4]]
     
     list[i][j] --> list[j][n-i-1]
     */
    func rotate(_ matrix: inout [[Int]]) {
        let n = matrix.count
        var list = matrix
        for i in 0..<matrix.count {
            for j in 0..<matrix[i].count {
                list[j][n-i-1] = matrix[i][j]
            }
        }
        
        for i in 0..<matrix.count {
            for j in 0..<matrix[i].count {
                matrix[i][j] = list[i][j]
            }
        }
    }
    
    /*
     圈地旋转
     
     */
}
